package com.hfb.mashibing.alip8.diamondsquarealgorithm.class01;


import java.util.Stack;

/**
 * 算法：单调栈的应用
 *
 * 问题：
 * 一个数组中子数组的累计和与最小值的乘积叫作指标A,给定一个正数数组,
 * 请返回这个数组中,A的最大值
 *
 *
 *
 *
 * 5 3 2 1 6 7 8 4
 * 由于是要求子数组中最小值与该子数组的和的乘积，所以我们规定，遍历这个数组
 * 规定遍历到的数组的每个元素都要求，这个元素是当前子数组中最小的，然后找到所有满足这个条件的子数组，从而求得当前数字的最大A
 * 当遍历完数组中每一个数字时，每个数字都会得到一个最大的A,那么整个数组的的最大A就在其中：
 * 为什么？因为整个数组的最大八，肯定是拿其中的一个数字，寻找以这个数字作为最小值的子数组，并且这个数字与该子数组的乘积要最大
 * 既然我们都已经把每一个数字都遍历了，那么值肯定在其中
 * 当遍历到5时，要求子数组要以5为最小值那么这样的子数组只有一个[5]，即本身构成的子数组，A值为5*5=25
 * 当遍历到3时，此时存在5,3]和[3]，A值分别为(5+3)*3=24和3*3=9，取最大的A=24
 * 当遍历到2时，此时存在[2]，[2,3]，[2,3,5]最大的那个是[5,3,2]即A为10*2=20
 * 当遍历到1时，子数组应该是全部[5,3,2,1,6,7,8,4，A为36*1=136
 * 当遍历到6时，子数组应该是[6]，[6,7,81，[6,7]最大的那个为(6+7+8)*6=126
 * 这样得到悔个数字的最大A
 * 最终整个数组的A就是这些A中最大的那个山
 * 接下来就是如何寻找以当前数字最小的子数组：
 * 比如但我们遍历到6时，我们是依据什么来得到子数组中是以6为最小值的呢？
 * 此时可以利用单调栈，即6左边比6小的且最近的数字1不能包含，6右边比6小的且最近数字4不能包含：
 * 这样中间的数字6,7,8就是可以作为子数组，且6是其中最小的那个
 *
 *
 */

public class Code04_AllTimesMinToMax {

    /**
     * 暴力法：用对数器来验证max2是否是正确
     * @param arr
     * @return
     */
    public static int max1(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int minNum = Integer.MAX_VALUE;
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                    minNum = Math.min(minNum, arr[k]);
                }
                max = Math.max(max, minNum * sum);
            }
        }
        return max;
    }

    /**
     * 算法
     * @param arr
     * @return
     */
    public static int max2(int[] arr) {
        int size = arr.length;
        int[] sums = new int[size];
        sums[0] = arr[0];
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int j = stack.pop();
                max = Math.max(max,
                    (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            max = Math.max(max,
                (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()]))
                    * arr[j]);
        }
        return max;
    }

    public static int[] gerenareRondomArray() {
        int[] arr = new int[(int) (Math.random() * 20) + 10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 101);
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 2000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = gerenareRondomArray();
            if (max1(arr) != max2(arr)) {
                System.out.println("FUCK!");
                break;
            }
        }
    }
}
